package 最后24大厂仿真;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

public class FZ1牛牛的三元组问题 {

    static class Solution {
        public int[][] findTriplets(int[] nums) {
            ArrayList<ArrayList<Integer>> res = new ArrayList<>();
            Arrays.sort(nums);
            for (int i = 0; i < nums.length; i++) {
                int index = 0;
                ArrayList<Integer> temp = new ArrayList<>();
                dps(res, nums, temp, index);
            }
            int[][] ans = new int[res.size()][3];
            for (int i = 0; i < res.size(); i++) {
                ArrayList<Integer> temp = res.get(i);
                for (int j = 0; j < 3; j++) {
                    ans[i][j] = temp.get(j);
                }
            }
            return ans;
        }

        private void dps(ArrayList<ArrayList<Integer>> res, int[] nums, ArrayList<Integer> temp, int index) {
            if (temp.size() == 3 && sum(temp) == 0 && check(res, temp)) {
                res.add(new ArrayList<>(temp));
            }
            if (index < nums.length && temp.size() < 3) {
                temp.add(nums[index]);
                dps(res, nums, temp, index + 1);
                temp.remove(temp.size() - 1);
                dps(res, nums, temp, index + 1);
            }
        }

        private int sum(ArrayList<Integer> list) {
            int sum = 0;
            for (int i = 0; i < list.size(); i++) {
                Integer num = list.get(i);
                sum += num;
            }
            return sum;
        }

        private boolean check(ArrayList<ArrayList<Integer>> res, ArrayList<Integer> temp) {
            HashMap<Integer, Integer> tempFreq = getFrequence(temp);
            for (int i = 0; i < res.size(); i++) {
                ArrayList<Integer> tar = res.get(i);
                HashMap<Integer, Integer> tarFreq = getFrequence(tar);
                if (tarFreq.equals(tempFreq)) {
                    return false;
                }
            }
            return true;
        }

        private HashMap<Integer, Integer> getFrequence(ArrayList<Integer> temp) {
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < temp.size(); i++) {
                Integer num = temp.get(i);
                map.put(num, map.getOrDefault(num, 0) + 1);
            }
            return map;
        }

    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {-1, 0, 1, 2, -1, -4};
        int[][] triplets = solution.findTriplets(nums);
        for (int i = 0; i < triplets.length; i++) {
            System.out.println(Arrays.toString(triplets[i]));
        }

    }

    public int[][] findTriplets(int[] nums) {
        // write code here
        // 排序
        Arrays.sort(nums);
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            // 判断是否相等
            if (i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }
            // 设置下标位置
            int index1 = i + 1;
            int index2 = nums.length - 1;
            while (index1 < index2) {
                // 求和
                int sum = nums[i] + nums[index1] + nums[index2];
                if (sum == 0) {
                    // 判断结果是否相等
                    list.add(new int[]{nums[i], nums[index1], nums[index2]});
                    while (index1 < index2 && nums[index1 + 1] == nums[index1]) {
                        index1 = index1 + 1;
                    }
                    while (index1 < index2 && nums[index2] == nums[index2 - 1]) {
                        index2 = index2 - 1;
                    }
                    index1 = index1 + 1;
                    index2 = index2 - 1;
                } else if (sum < 0) {
                    // 小于0则第一个坐标+1
                    index1 = index1 + 1;
                } else {
                    index2 = index2 - 1;
                }
            }
        }
        return list.toArray(new int[0][0]);
    }

}
